/*
 * @lc app=leetcode.cn id=2179 lang=typescript
 *
 * [2179] 统计数组中好三元组数目
 */

// @lc code=start

// 树状数组，维护当前元素前有几个元素在num1和num2中出现在当前元素的前面
class BIT {
  data: number[];
  n: number;
  constructor(n: number) {
    this.n = n;
    this.data = new Array(n + 1).fill(0);
  }
  private lowbit(x: number) {
    return x & -x;
  }

  add(x: number, val: number): void {
    while (x <= this.n) {
      this.data[x] += val;
      x += this.lowbit(x);
    }
  }

  query(x: number): number {
    let sum = 0;
    while (x) {
      sum += this.data[x];
      x -= this.lowbit(x);
    }
    return sum;
  }
}

function goodTriplets(nums1: number[], nums2: number[]): number {
  let n = nums1.length;
  // 构建树状数组，维护num2元素某个阶段是否出现，出现的话标记为1
  const ind = new BIT(n);

  // num2 元素的下标的映射关系
  const inxMap = new Map<number, number>();
  for (let i = 0; i < n; i++) {
    inxMap.set(nums2[i], i);
  }

  let ans = 0;
  // 遍历nums1，计算结果
  for (let i = 0; i < n; i++) {
    // 当前元素在nums2中的下标
    const j = inxMap.get(nums1[i]);
    // 当前元素在nums1和nums2中前面出现的相同元素个数
    const cnti = ind.query(j + 1);
    // 当前元素在nums1和nums2中前面出现的相同不同元素个数
    const diff = i - cnti;
    // 当前元素在nums1和nums2中后面出现的相同元素个数
    const cntj = n - j - 1 - diff;
    // 更新答案
    ans += cnti * cntj;
    // 更新树状数组
    ind.add(j + 1, 1);
  }
  return ans;
}
// @lc code=end
